use std::cmp::Ordering;
use std::fmt;
use std::fs::File;
use std::io::prelude::*;
use std::io::BufReader;
use std::ptr::NonNull;

use data_structure::prelude::*;

#[derive(Clone, Eq, Default)]
struct Record {
    string: String,
    count: u64,
}

impl PartialOrd for Record {
    fn partial_cmp(&self, other: &Record) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for Record {
    fn cmp(&self, other: &Record) -> Ordering {
        self.count.cmp(&other.count)
    }
}

impl PartialEq for Record {
    fn eq(&self, other: &Record) -> bool {
        self.count.eq(&other.count)
    }
}

impl fmt::Debug for Record {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "<{} - {}>", self.string, self.count)
    }
}

struct TrieNode {
    count: u64,
    keys: Vec<u8>,
    children: Vec<NonNull<TrieNode>>,
}

struct TrieTree {
    root: NonNull<TrieNode>,
    key_size: u64,
}

impl TrieTree {
    #[inline]
    fn create_node() -> NonNull<TrieNode> {
        let boxed = Box::new(TrieNode {
            count: 0,
            keys: Vec::new(),
            children: Vec::new(),
        });
        Box::leak(boxed).into()
    }

    #[inline]
    pub fn new() -> Self {
        Self {
            root: Self::create_node(),
            key_size: 0,
        }
    }

    #[inline]
    pub fn parse(&mut self, key_string: &str) {
        unsafe {
            let mut node = self.root.as_ptr();
            for byte in key_string.bytes() {
                if let Some(idx) = (*node).keys.iter().position(|k| *k == byte) {
                    node = (*node).children[idx].as_ptr()
                } else {
                    let n = Self::create_node();
                    (*node).keys.push(byte);
                    (*node).children.push(n);
                    node = n.as_ptr();
                }
            }
            if (*node).count == 0 {
                self.key_size += 1;
            }
            (*node).count += 1;
        }
    }

    #[inline]
    pub fn analysis(&self, top_max: u64, top_min: u64) -> (Vec<Record>, Vec<Record>) {
        assert!(top_max > 0 && top_min > 0);
        let mut min_heap: MinHeap<List<Record>> = MinHeap::new();
        let mut max_heap: MaxHeap<List<Record>> = MaxHeap::new();
        let mut ident = String::new();
        let mut stack: Stack<Table<DNode<(usize, u8, NonNull<TrieNode>)>>> = Stack::new();
        stack.push((0, 0, self.root));
        while let Some((mut trace, byte, node)) = stack.pop() {
            unsafe {
                if byte > 0 {
                    ident.push(byte as char);
                }
                let count = (*node.as_ptr()).count;
                if count > 0 {
                    let rec = Record {
                        string: ident.clone(),
                        count: count,
                    };
                    if min_heap.size() < top_max {
                        min_heap.push(rec.clone());
                    } else if min_heap.value().unwrap() < rec {
                        min_heap.update(Some(rec.clone()));
                    }

                    if max_heap.size() < top_min {
                        max_heap.push(rec.clone());
                    } else if max_heap.value().unwrap() > rec {
                        max_heap.update(Some(rec));
                    }
                }
                match (*node.as_ptr()).keys.len() > 0 {
                    true => (*node.as_ptr())
                        .keys
                        .iter()
                        .zip((*node.as_ptr()).children.iter())
                        .for_each(|(&k, &n)| {
                            stack.push((trace + 1, k, n));
                            trace = 0;
                        }),
                    false => ident.truncate(ident.len() - trace),
                }
            }
        }
        let mut min_vals = Vec::<Record>::with_capacity(top_min as usize);
        let mut max_vals = Vec::<Record>::with_capacity(top_max as usize);
        while let Some(rec) = min_heap.pop() {
            max_vals.push(rec)
        }
        while let Some(rec) = max_heap.pop() {
            min_vals.push(rec)
        }
        (max_vals, min_vals)
    }
}

#[test]
fn trie() {
    let mut tree = TrieTree::new();
    let file = File::open("assets/tales.txt").unwrap();
    let reader = BufReader::new(file);
    for result in reader.lines() {
        if let Ok(line) = result {
            let mut string: &str = &line;
            string = string.trim();
            let words: Vec<&str> = string.split(' ').collect();
            for word in words.into_iter() {
                let mut lc = word.to_ascii_lowercase();
                lc.retain(|c| c >= 'a' && c <= 'z');
                if lc.len() > 0 {
                    tree.parse(&lc);
                }
            }
        }
    }
    let (max_vals, min_vals) = tree.analysis(10, 10);
    println!("top 10 max values: {:?}", max_vals);
    println!("top 10 min values: {:?}", min_vals);
    assert_eq!(
        vec![827, 860, 896, 1032, 1202, 1260, 1396, 2016, 3370, 5337],
        max_vals
            .into_iter()
            .map(|rec| rec.count)
            .collect::<Vec<u64>>(),
    );
}
